package 算法.字符串.哈夫曼编码;

import java.util.ArrayList;
import java.util.List;

import sun.security.util.Length;
import util.LogUtils;
import util.TraverseUtils;

import com.sun.corba.se.impl.orbutil.graph.Node;

import edu.princeton.cs.algs4.BinaryDump;
import edu.princeton.cs.algs4.BinaryIn;
import edu.princeton.cs.algs4.BinaryStdIn;
import edu.princeton.cs.algs4.BinaryStdOut;
import edu.princeton.cs.algs4.MinPQ;


/**
 * 【哈夫曼树  与 哈夫曼编码 】
 * 
 * @Date 2017-09-07 11：23
 * @author Administrator
 * @version
 */
public class Huffman {
	
	private Node root;
    //ASCII码共256个字符
    private static final int R = 256;
	//哈夫曼树的 节点
	private static class Node implements Comparable<Node> {
		public char ch;
		public int  fre;				//ch的频度
		public Node left, right;
		public Node(char ch, int fre, Node left, Node right) {
			super();
			this.ch = ch;
			this.fre = fre;
			this.left = left;
			this.right = right;
		}
		public boolean isLeaf()	{return left==null && right==null;}
		@Override
		public String toString() {
			return "Node [ch=" + ch + ", fre=" + fre + ", left=" + left
					+ ", right=" + right + "]";
		}
		@Override
		public int compareTo(Node that) {
			if ( this.fre < that.fre)	return -1;
			else if(this.fre > that.fre)	return 1;
			else return 0;
		}
	}
	
	/**
	 * buildTire()：生成 哈夫曼树
	 * @param fre
	 * @return
	 */
	public Node buildTrie(int[] fre) {
		MinPQ<Node> pq = new MinPQ<Huffman.Node>();		//优先队列，小谷堆
		//将所有字符存入优先队列中
		for (int ch = 0; ch < fre.length; ch ++)  {
			if(fre[ch] > 0) {
				pq.insert(new Node((char) ch, fre[ch], null, null));
			}
		}
		LogUtils.println("pq size", pq.size());
		//生成哈夫曼树
		while(pq.size() > 1) {
			Node lNode = pq.delMin(), rNode = pq.delMin();
			Node parent = new Node('\0', lNode.fre+rNode.fre, lNode, rNode);	//合成一个节点，ch随意~
			pq.insert(parent);
		}
		return pq.delMin();			//返回生成的 哈夫曼树
	}
	
	public String[] buildCode() {
		String[] st  = new String[R];
		for(int i = 0; i < st.length; i ++)	st[i] = "";
		buildCode(root, st, "");
		return st;
	}
	
	/**
	 * buildCode()：遍历整个哈夫曼树，生成编码表
	 * 		类似于前序遍历
	 * @param st 生成的编码表
	 * @param x  根节点
	 * @param strBits
	 * @return
	 */
	
	public void buildCode(Node x, String[] st, String strBits) {
		if (x.isLeaf()) {
			st[x.ch] = strBits;
			return;
		}
		buildCode(x.left,  st, strBits+'0');
		buildCode(x.right, st, strBits+'1');

	}
	
	/**
	 * writeTrie()：遍历整个哈夫曼树，将字符转换为8位bit输出
	 * 	如果遇到叶子节点输出前导位1(true)，否则遇到的是中间节点输出前导位0(false)
	 * 		类似于前序遍历
	 * @param st 生成的编码表
	 * @param x  根节点
	 * @param strBits
	 * @return
	 */
	public void writeTrie(Node x) {
		if(x.isLeaf()) {
			BinaryStdOut.write(true);		//写入到输出流
			BinaryStdOut.write(x.ch, 8);
			return;
		}
		BinaryStdOut.write(false);
		writeTrie(x.left);
		writeTrie(x.right);
	}
	
	//MyMethod:
	public void expand(Node x, char[] input, String[] st) {
		
		for (int i = 0; i < input.length; i ++) {
				expand(x, st[input[i]], 0);
//				char[] code = st[i].toCharArray();

		}
	}
	
	/**
	 * expand() 展开(解码)	
	 * 	eg：将 "101" 解码为 '!'
	 * @param x
	 */
	//MyMethod:
	public void expand(Node x, String strBits, int offset) {
		if (x.isLeaf())	{
			LogUtils.println("expand", Character.valueOf(x.ch));
			return;
		}
		if(strBits.charAt(offset) == '0')	expand(x.left,  strBits, offset+1);
		if(strBits.charAt(offset) == '1')	expand(x.right, strBits, offset+1);
	}
	
	public void expand() {
        // read in Huffman trie from input stream
        Node root = readTrie(); 

        // number of bytes to write
        int length = BinaryStdIn.readInt();

        // decode using the Huffman trie
		for (int i = 0; i < length; i ++) {
			Node x = root;
			while (!x.isLeaf()) {
				boolean bit = BinaryStdIn.readBoolean();
				if (bit)	x = x.right;
				else x = x.left;
			}
			BinaryStdOut.write(x.ch, 8);
		}
		BinaryStdOut.close();
	}
	
	
	/**
	 * readTrie()： writeTrie()的逆方法：
	 * 		
	 * @param st 生成的编码表
	 * @param x  根节点
	 * @param strBits
	 * @return
	 */
	public static Node readTrie() {
		boolean isLeaf = BinaryStdIn.readBoolean();					//读取前导0
		if(isLeaf)	return new Node(BinaryStdIn.readChar(), -1, null, null);
		else		return new Node('\0', -1, readTrie(), readTrie());
	}
	
	
	/**
	 * compress()：Huffman压缩
	 */
	public void compress() {
//		char[] input = "it was the best of times it was ".toCharArray();
		char[] input = "ABRACADABRA!".toCharArray();
	
		//字符频度数组
		int[] fre = new int[R];
		for (int i = 0; i < input.length; i ++) {
			char curCh = input[i];
			fre[curCh] ++;
		}
		root = buildTrie(fre);

		traverse(root);
		
		String[] st = buildCode();
		
		for (int i = 0; i < st.length; i++) {
			String string = st[i];
//			LogUtils.println("st",st[i]);
		}
		
		//前序遍历输出
		expand(root, input, st);
		
		//(递归地)打印编码用的单词查找树
		writeTrie(root);
		
		//打印字符总数
//		BinaryStdOut.write(input.length);
		
		//使用哈夫曼编码处理input

		BinaryStdOut.close();                //关闭流 
	}
	
	/**
	 * 前序遍历
	 */
	public void traverse(Node root) {
		if (root == null) return;
		LogUtils.println("Huffman 前序遍历", root);
		traverse(root.left);

		traverse(root.right);
	}

	public static void main(String[] args) {
		new Huffman().compress();
	}
}
